package code.oldCode.feishuSpecializedTraining.dynamic;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 26029
 * @date 2025/3/24
 * @description
 */
public class MyDP5 {
    // 279. 完全平方数
    public int numSquares(int n) {
        // 首先抽象为背包问题：背包为[1, 4, 9, 16, ..., x] x < n，背包大小为n，可复选，求填满背包的最小物品数
        // 再抽象为爬楼梯问题：爬到n，每次爬[1,4,9,16,...,x]层，求最少爬行次数
        List<Integer> items = new ArrayList<>();
        for (int i = 1; i * i <= n; i++) {
            items.add(i * i);
        }
        // dp[i]表示爬到i层所需最少步数
        int[] dp = new int[n + 1];
        // 爬楼梯问题，外遍历楼层，内遍历爬楼数
        dp[0] = 0;
        for (int i = 1; i <= n; i++) {
            dp[i] = Integer.MAX_VALUE;
            for (int item : items) {
                if (i >= item)
                    dp[i] = Math.min(dp[i], dp[i - item] + 1);
                // 如果item已经比i大了，就break了，因为这个item是递增的[1,4,9,...]
                else
                    break;
            }
        }
        return dp[n];
    }

    // 139. 单词拆分
    public boolean wordBreak(String s, List<String> wordDict) {
        // 背包问题：背包是s？item是wordDict？求是否有一个顺序可以填满背包
        // 抽象为爬楼梯？
        int len = wordDict.size();
        // dp[i] 表示wordDict是否可以表示s的前i个char
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        // 先遍历楼层
        for (int i = 1; i <= s.length(); i++) {
            // 再遍历步数
            for (int j = 0; j < len; j++) {
                String word = wordDict.get(j);
                if (word.length() <= i && s.substring(i - word.length(), i).equals(word)) {
                    dp[i] = dp[i] || dp[i - word.length()];
                }
            }
        }
        return dp[s.length()];
    }
}
